Vì Turing không chịu học các môn ngoài toán và khoa học, ông không nhận được học bổng để học tại Học viện Trinity của Đại học Cambridge, mà phải học tại King's college của Đại học Cambridge từ năm 1931 đến 1934 và tốt nghiệp đại học với bằng danh dự. Năm 1935 ông được chọn làm nghiên cứu sinh tại trường King's, nhờ chất lượng của luận văn trong đó ông đã chứng minh định lý giới hạn trung tâm,[10] mặc dù ông không nhận ra rằng nó đã được chứng minh năm 1922 bởi Jarl Waldemar Lindeberg.[11]

Năm 1928, nhà toán học người Đức David Hilbert kêu gọi sự chú ý đến Entscheidungsproblem (bài toán quyết định). Trong bài viết nổi tiếng của ông, tựa đề "Các số khả tính, với áp dụng trong Vấn đề về lựa chọn" (On Computable Numbers, with an Application to the Entscheidungsproblem) - thuật toán lôgic - (nộp ngày 28 tháng 5 năm 1936 và nhận được ngày 12 tháng 11),[12] Turing tái dựng lại kết quả của Kurt Gödel hồi năm 1931 về những hạn chế trong chứng minh và tính toán, thay đổi thuật ngữ tường trình số học chính quy của Gödel, bằng cái mà ngày này người ta gọi là máy Turing, một dụng cụ chính quy và đơn giản. Ông đã chứng minh rằng một cái máy như vậy sẽ có khả năng tính toán bất cứ một vấn đề toán học nào, nếu vấn đề ấy có thể được biểu diễn bằng một thuật toán. Máy Turing, cho đến nay, vẫn là một vấn đề nghiên cứu trung tâm trong lý thuyết về máy tính. Ông còn tiếp tục chứng mình rằng vấn đề về lựa chọn (Entscheidungsproblem) là một vấn đề không giải được, bằng cách đầu tiên chứng minh rằng bài toán dừng trong máy của Turing là bất khả định; nói chung, không thể quyết định bằng một thuật toán liệu một máy Turing cho trước có bao giờ dừng hay không. Tuy chứng minh của ông được đăng công khai sau chứng minh tương tự của Alonzo Church đối với phép tính lambda (lambda calculus), chứng minh của Turing được coi là dễ hiểu và trực giác hơn. Chứng minh của ông còn có một đóng góp quan trọng là đưa ra khái niệm "máy Turing vạn năng" (Universal (Turing) Machine), với ý tưởng rằng một máy như vậy có thể làm bất cứ việc gì mà các máy khác làm được. Bài viết còn giới thiệu khái niệm về số khả định (definable number). Trong hồi ký, Turing viết rằng ông đã rất thất vọng về những phản hồi cho bài báo năm 1936, khi chỉ có hai người có phản hồi, là Heinrich Scholz và Richard Bevan Braithwaite.

Từ tháng 9 năm 1936 đến tháng 7 năm 1938, ông cư trú tại đại học Princeton, nghiên cứu dưới sự hướng dẫn của Alonzo Church. Năm 1938, ông đạt được bằng Tiến sĩ tại trường này. Luận văn của ông giới thiệu quan niệm tính toán tương đối (relative computing). Trong khái niệm này, máy Turing được mở rộng bằng cách cho phép hỏi máy tiên tri (oracle machine), cho phép nghiên cứu những bài toán không thể giải được bằng máy Turing.

Sau khi quay trở lại Cambridge vào năm 1939, ông dự thính bài giảng của Ludwig Wittgenstein về nền tảng của toán học (foundations of mathematics). Hai người tranh cãi và bất đồng ý kiến một cách kịch liệt. Trong khi Turing bảo vệ lập trường của chủ nghĩa hình thức (formalism), thì Wittgenstein lại tranh cãi rằng toán học được đánh giá quá mức, và bản thân nó không thể tìm ra bất cứ một chân lý cuối cùng nào (absolute truth) (Wittgenstein 1932/1976).